//给定一个二叉树，它的每个结点都存放着一个整数值。
//
// 找出路径和等于给定数值的路径总数。
//
// 路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
//
// 二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。
//
// 示例：
//
// root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
//
//      10
//     /  \
//    5   -3
//   / \    \
//  3   2   11
// / \   \
//3  -2   1
//
//返回 3。和等于 8 的路径有:
//
//1.  5 -> 3
//2.  5 -> 2 -> 1
//3.  -3 -> 11
//
// Related Topics 树
// 👍 884 👎 0

/**
 * @author DaHuangXiao
 */
package leetcode.editor.cn;

import java.util.HashMap;
import java.util.Map;

public class PathSumIii {
    public static void main(String[] args) {
        Solution solution = new PathSumIii().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private int target;
    private int total;
    private int maxLen;
    private Map<Integer,Integer> map;
    public int pathSum1(TreeNode root, int targetSum) {
        map = new HashMap<>();
        target=targetSum;
        total=0;
        dfs_out(root);
        return maxLen;
    }
    public void dfs_out(TreeNode root){
        if (root==null){return;}
        dfs(root);
        dfs_out(root.left);
        dfs_out(root.right);
    }
    public void dfs(TreeNode root){

        if (root==null){return;}
        if (total+root.val==target){
            maxLen++;
        }
        total+=root.val;
        dfs(root.left);
        dfs(root.right);
        total-=root.val;

    }
    public int pathSum(TreeNode root, int targetSum) {
        map = new HashMap<>();
        target=targetSum;
        maxLen =0;
        map.put(0,1);
        dfs2(root,0);
        return maxLen;
    }

    private void dfs2(TreeNode root,int tot) {
        if (root==null){
            return;
        }
        int curSum = tot+root.val;

        maxLen+=map.getOrDefault(curSum-target,0);

        map.put(curSum,map.getOrDefault(curSum,0)+1);
        dfs2(root.left,curSum);
        dfs2(root.right,curSum);
        map.put(curSum,map.get(curSum)-1);
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}